package com.leet.tree;

import java.util.*;

public class AverageOfLevels {
    public List<Double> averageOfLevels(TreeNode root) {
        Deque<TreeNode> q = new LinkedList<>();
        q.offer(root);
        List<Double> ans = new ArrayList<>();
        // accLine有可能是double
        double accLine = 0;
        while(!q.isEmpty()){
            double size = q.size();
            accLine = 0;
            for(int i = 0;i < size; ++i){
                TreeNode head = q.poll();
                if(head!=null) accLine += head.val;
                if(head.left != null) q.offer(head.left);
                if(head.right != null) q.offer(head.right);
            }
            ans.add((accLine / size));
        }
        return ans;
    }
}
